Метод простого перебора

Будем предполагать, что искомый минимум является строгим, то есть $ f(x)>f(x^*)$ при всех $ x\ne x^*$, $ x\in[a;b]$, и других точек локального минимума на отрезке нет. Предположим также, что точка минимума $ x^*$ -- внутренняя точка отрезка. Зададимся точностью $ {\varepsilon}$, с которой будем приближённо отыскивать $ x^*$. Приближённое значение точки минимума обозначим $ \wt x$, то есть $ \wt x$ -- это такое число, что

$\displaystyle \vert\wt x-x^*\vert<{\varepsilon}.$

Простейший способ обнаружить точку $ x^*$ с точностью $ {\varepsilon}$ -- это перебирать точки $ x_i$ отрезка $ [a;b]$ с шагом $ h\leqslant {\varepsilon}$, начиная с $ x_0=a$, до тех пор, пока не будет выполнено условие $ f(x_{i+1})>f(x_i)$, то есть пока функция не начнёт возрастать после точки минимума. При этом точка $ x^*$ может оказаться либо на отрезке $ [x_{i-1};x_i]$, либо на отрезке $ [x_i;x_{i+1}]$ (cм. следующий чертёж):

Рис.9.15.Два случая расположения точки минимума при $ f(x_{i+1})>f(x_i)$


Если теперь положить $ \wt x=x_i$, то в любом из двух случаев будет выполнено неравенство $ \vert\wt x-x^*\vert\leqslant h\leqslant {\varepsilon}$, то есть точка минимума будет найдена с нужной нам точностью. За приближённое значение $ f_{\min}$ нужно теперь взять $ f(\wt x)=f(x_i)$. Дополнительного вычисления функции при этом не потребуется, поскольку значение $ f(x_i)$ уже было найдено ранее.

Если не предполагать, что локальный минимум на отрезке $ [a;b]$ только один и что точка минимума -- внутренняя точка отрезка, то придётся изменить метод так: вычислять значения $ f(x_i)$ до тех пор, пока точка $ x_i$ не достигнет правого конца отрезка -- точки $ b$; на каждом шаге сравнивать текущее значение $ f(x_i)$ с минимальным из предыдущих значений $ m$, заменяя это минимальное значение $ m$ на $ f(x_i)$ при $ m>f(x_i)$. Наконец, вычислить $ f(b)$ (если точка $ b$ не совпадает с последней из точек $ x_i$) и также сравнить с минимальным из предыдущих значений. После этой процедуры $ m$ будет приближённо равно $ f_{\min}$, а та точка, в которой получено значение функции, равное $ m$ -- приближённым значением $ \wt x$ точки минимума $ x^*$.

Заметим, что метод простого перебора при поиске точки экстремума аналогичен методу простого перебора при поиске корня уравнения $ f(x)=0$.